package PriorQueue;

import java.util.*;

class Student implements Comparable<Student> {
    public int age;
    public String name;

    public Student(String name,int age) {
        this.age = age;
        this.name = name;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return age == student.age && Objects.equals(name, student.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(age, name);
    }

    @Override
    public int compareTo(Student o) {
        return o.age - this.age;
    }
}
class cmp implements Comparator<Student> {

    @Override
    public int compare(Student o1, Student o2) {
        return o1.name.compareTo(o2.name);
    }
}
class Maxcmp implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}
public class Text {
    /*topK问题
    * 找前k个最大的元素
    * 时间复杂度：N*logK
    * */

    public int[] smallestK(int[] array, int k) {
        int[] ret = new int[k];
        if (ret == null || k == 0) {
            return ret;
        }
        Maxcmp maxcmp = new Maxcmp();
        Queue<Integer> maxHeap = new PriorityQueue<Integer>(maxcmp);
        //1.遍历前k个元素，放到一个数组中
        for (int i = 0; i < k; i++) {
            maxHeap.offer(array[i]);
        }
        //2.建立大根堆，遍历k之后的元素，和堆顶元素进行比较，如果比堆顶元素大就交换堆顶元素和数组中的哪个元素
        for (int i = k; i < array.length; i++) {
            if (maxHeap.peek() > array[i]) {
                maxHeap.poll();
                maxHeap.offer(array[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            ret[i] = maxHeap.poll();
        }
        return ret;
    }

    public static void main(String[] args) {
        TextHeap textHeap = new TextHeap();
        int[] array = {27,15,19,18,28,34,65,49,25,37};
        textHeap.initElem(array);
        textHeap.createHeap();//创建大根堆
        textHeap.heapSort();
        System.out.println("vscsd");
    }
    public static void main4(String[] args) {
        Student student1 = new Student("zhangsan",18);
        Student student2 = new Student("zhangsan",18);
        //虽然肉眼看这两个对象我们认为是同一个人，但是在比较的时候
        System.out.println(student1 == student2);
        System.out.println(student1.equals(student2));
        /*他俩是不相等的，因为它是一个引用 ，在内存上开辟的是两块空间
        同样的，equals也是，这个类本身是没有equals方法的，所有类默认继承object类，
        所以equals是object类中的方法，但是还是去同样的比较，当我们重写了equals方法，
        默认就会调用当前类的equals方法，*/
    }
    public static int[] maxK(int[] array, int k) {
        int[] ret = new int[k];
        if (ret == null || k == 0) {
            return ret;
        }
        //这个是优先级队列，底层是一个最小堆，把数组的元素加进来之后，它会把数组的元素简称一个最小堆
        Queue<Integer> minHeap = new PriorityQueue<>();
        //1.遍历数组的前k个元素，放到堆中  时间：K * logK
        for (int i = 0; i < k; i++) {
            minHeap.offer(array[i]);
        }
        //2.遍历剩下的k-1个元素，和堆顶元素进行比较   时间：（N-K）*logK
        //如果堆顶元素比数组中的这个元素小，堆顶元素就出堆，将堆顶元素换成数组中的哪个元素
        for (int i = k; i <array.length; i++) {
            if (minHeap.peek() < array[i]) {
                minHeap.poll();
                minHeap.offer(array[i]);
            }
        }
        //存储结果
        for (int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }
        return ret;
    }
    public static void main3(String[] args) {
        int[] array = {56,65,69,7,76,878,34,88};
        //找前k个最大的元素
        int[] ret = maxK(array,3);
        System.out.println(Arrays.toString(ret));
    }
    public static void main2(String[] args) {
        List<Integer> list = new ArrayList<>();
        //如果这个list中有数据，
        //弹出的元素是2，默认的是一个小根堆
        Queue<Integer> priorityQueue1 = new PriorityQueue<>(list);//有一个带一个参数的构造方法
        //可以放入list，这个小根堆会默认的把list数组中的数据拿过来，然后创建一个小根堆
        priorityQueue1.offer(2);
        priorityQueue1.offer(10);
        System.out.println(priorityQueue1.poll());
    }
    public static void main1(String[] args) {
        TextHeap textHeap = new TextHeap();
        int[] array = {27,15,19,18,28,34,65,49,25,37};
        textHeap.initElem(array);
        textHeap.createHeap();//创建大根堆
        System.out.println("cssccdcssd");
        textHeap.pop();
        System.out.println("fsffaf");
    }
}
